﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Ahao.LeetCode._0100_0199.demo143
{
    internal class Class143
    {

        public void reorderList(ListNode head)
        {
            if (head == null)
            {
                return;
            }
            List<ListNode> list = new List<ListNode>();
            ListNode node = head;
            while (node != null)
            {
                list.Add(node);
                node = node.next;
            }
            int i = 0, j = list.Count - 1;
            while (i < j)
            {
                list[i].next = list[j];
                i++;
                if (i == j)
                {
                    break;
                }
                list[j].next = list[i];
                j--;
            }
            list[i].next = null;
        }



        public void reorderList2(ListNode head)
        {
            if (head == null)
            {
                return;
            }
            ListNode mid = middleNode(head);
            ListNode l1 = head;
            ListNode l2 = mid.next;
            mid.next = null;
            l2 = reverseList(l2);
            mergeList(l1, l2);
        }

        public ListNode middleNode(ListNode head)
        {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        public ListNode reverseList(ListNode head)
        {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null)
            {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }

        public void mergeList(ListNode l1, ListNode l2)
        {
            ListNode l1_tmp;
            ListNode l2_tmp;
            while (l1 != null && l2 != null)
            {
                l1_tmp = l1.next;
                l2_tmp = l2.next;

                l1.next = l2;
                l1 = l1_tmp;

                l2.next = l1;
                l2 = l2_tmp;
            }
        }


    }


    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x)
        {
            val = x;
            next = null;
        }
    }
}
